我才六年级，我还不太熟悉dp呢，喷可以，但喷轻点谢谢
还有本篇未完全使用标准的Markdown规范文章模板及LaTeX，不要骂！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
单调性问题简介
先从一道经典单调性问题：最长上升子序列开始说起
很多人可能觉得：“为什么这种文章中会出现如此简单的题目？” 你等会就知道了
先看最经典写法：
时间复杂度： O(n2)O(n^2)O(n2)
这个时间复杂度是不太理想的
我们今天的方法就是要将代码的时间复杂度优化到 O(nlogn)O(n log n)O(nlogn)
实际上，绝大多数优化方法优化的都是时间复杂度/空间复杂度
* 那如何将代码代码的时间复杂度优化到 O(nlogn)O(n log n)O(nlogn) 呢？
先回顾问题：
> 输入n个数（对于单调性优化类题来讲，n≤106n \le 10^6n≤106），输出其最长上升子序列长度
用二分
你想啊，既然都是“单调性问题”了，那不自然可以和二分结合吗？
1. dp含义的更改
dp数组此时必须要包含结尾数字信息（xxx情况下，结尾数字是…）
要从dp[i]表示以第i个数为结尾的最长上升子序列长度
转变为
dp[i] = x表示最长上升子序列长度为 iii 的情况下，结尾数字是 xxx
还不对！结尾数字可能有很多，因此要改成
dp[i] = x表示最长上升子序列长度为 iii 的情况下，结尾数字最小是 xxx
> Q1：为什么是“结尾数字最小是 xxx”？
> A1：因为结尾数字越多，前面数字的可能性越大；可能性越大，最长上升子序列的长度就有可能越长
2. 状态转移方程的更改
我们考虑可能造成的影响:
要么就是使最长上升子序列长度+1
那么我们就需要一个变量len，记录当前最长上升子序列的长度，并更新
也就是当 ai>dplena_i > dp_{len}ai >dplen 时，要进入这种情况
要么就是优化前面的最长上升子序列
也就是当 ai<dplena_i < dp_{len}ai <dplen 时，要进入这种情况
这时便于理解，举个栗子🌰：
A=[1, 2, 5, 8, 4, 7]A = [1,\ 2,\ 5,\ 8,\ 4,\ 7]A=[1, 2, 5, 8, 4, 7]
到 444 这一项时，无法显然无法替换 888，可以替换 5、2、15、2、15、2、1，但替换 2、12、12、1是没有用的
所以如果 dpj1, dpj2,⋯dpjn>a[i]dp_{j_1},\ dp_{j_2}, \cdots dp_{j_n} > a[i]dpj1 , dpj2 ,⋯dpjn >a[i] ，此时要替换最小的那个
因为替换其他的是没有用的，甚至会不合法（就是例子中的 444 只能替代 555，不能替代 888，要不然会不合法）
此时需要 二分 查找第一个比 aia_iai 大的数字
> Q1：为什么此时符合单调性？
> A1：因为dp的定义促使了成为符合单调性的队列
> Q2：为什么二分直接找到第一位大于 aia_iai 的位置idx就可以直接 dpidx=aidp_{idx}=a_idpidx =ai
> A2：因为本质上第一位大于 aia_iai 的位置idx就是 dp数组前idx项，更改dp前idx项的最小值为aia_iai 即可
3. 输出答案的更改
既然已经有一个变量len了，直接输出即可
4. 总结
所以更改后的O(nlogn)O(nlogn)O(nlogn)代码
